# author:高金磊
# datetime:2022/3/8 11:52
# class Solution:
#     def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
#         middle=[i[0] for i in matrix]
#         st_end=self.binary_plus(middle,target,0,len(middle))
#         if st_end[0]:
#             if st_end[1]==st_end[2]:
#                 return True
#             else:
#                 middle1=matrix[st_end[1]]
#                 middle2=matrix[st_end[1]]
#                 res1=self.binary_plus(middle1,target,0,len(middle1))
#                 if res1[0]:
#                     if res1[1]==res1[2]:
#                         return True
#                 res2=self.binary_plus(middle2,target,0,len(middle2))
#                 if res2[0]:
#                     if res2[1]==res2[2]:
#                         return True
#         return False
#     def binary_plus(self, matrix, target: int,st,end):
#         if st>=end:
#             if matrix[st]==target:
#                 return [True,st,st]
#             return [False,-1.-1]
#
#         if end-st==1:
#             return [True,st,end]
#         middle=int((st+end)/2)
#         if matrix[middle]==target:
#             return [True,middle,middle]
#         if matrix[middle]<target:
#             return self.binary_plus(matrix,target,middle+1,end)
#         else:
#             return self.binary_plus(matrix,target,st,middle-1)

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        middle=[i[0] for i in matrix]
        res=self.plus(middle,target,0,len(matrix))
        index=0
        if res[0]:
            return True
        else:
            if middle[res[1]]>target:
                index=res[1]-1
                if index<0:
                    return False
            else:
                index=res[1]
            return self.plus(matrix[index],target,0,len(matrix[index]))[0]

    def plus(self,nums,target,st,end):
        middle=int((st+end)/2)
        if nums[middle]==target:
            return [True,middle]
        if st>=end:
            return [False,st]
        if nums[middle]<target:
            return self.plus(nums,target,middle+1,end)
        else:
            return self.plus(nums,target,st,middle-1)



if __name__ == '__main__':
    print(111)
    pass